/**
 * 快速排序的思想是确定基准值，基于不同的基准值进行排序
 * @param {array} arr
 * @param {number} left
 * @param {number} right
 */
const quickSort = function (arr, left = 0, right = arr.length - 1) {
  if (arr.length > 1) {
    // 基于基准值排序后的指针索引
    const splitIdx = sortByBasisValue(arr, left, right)
    // 左侧超过一个元素才值得排序
    if (splitIdx > left + 1) {
      quickSort(arr, left, splitIdx - 1)
    }
    // 右侧超过一个元素才值得排序
    if (splitIdx < right) {
      quickSort(arr, splitIdx, right)
    }
  }
  return arr
}

/**
 * 根据基准值对数组进行排序
 * 每次排序后两个指针都在基准值处汇合
 */
function sortByBasisValue(arr, left, right) {
  // 选定中间值为基准值
  let basisValue = arr[Math.floor(left + (right - left) / 2)]
  // 初始化左右指针
  let i = left,
    j = right

  // 当两指针未相遇时
  while (i <= j) {
    // 在左侧找出不小于基准值的元素
    while (arr[i] < basisValue) {
      i++
    }
    // 在右侧找出不大于基准值的元素
    while (arr[j] > basisValue) {
      j--
    }
    // 找到了，且左右指针没有越过，则交换两个元素
    if (i <= j) {
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
      i++
      j--
    }
  }
  // 将左指针索引返回
  return i
}

const res = quickSort([3, 2, 1])
console.log(res)

export default quickSort
